package sword.offer;

/**
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值`1
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FortyTwo {
    /**
     * 使用动态规划思想
     * 第一步 定义数组元素的含义 通常含义就是我们要求的结果
     * 第二步 找出数组元素之间的关系式
     * 第三步 找出初始化值
     *
     * 定义dp[i]为  在原数组中以i结尾的子数组的和
     * 数组元素的关系  dp[i] = max(dp[i-1]+arr[i],arr[i]) 即 考虑是否将当前元素加入到上一个子数组中
     * 找出初始化值 每个元素都依赖于前一个做判断 所以初始化第一个元素即可 dp[0] = arr[0]
     *
     * 这道题可以做内存优化，因为方程式每次都仅仅依赖于前面的一个元素 可以取消数组 仅记录其依赖的数
     * */
    class Solution {
        public int maxSubArray(int[] nums) {
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            int max = dp[0];
            for (int i = 1; i<nums.length; i++){
                dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
                max = Math.max(dp[i], max);
            }
            return max;
        }
    }
}
